package com.mango.ch07;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class Combination {
	public static <T extends Comparable<? super T>> List<List<T>> findSortedCombinatinos(Collection<T> elements,
			int n) {
		System.out.println("当前n是"+n);
		List<List<T>> result = new ArrayList<List<T>>();
		// 处理递归的初始步骤
		if (n == 0) {
			result.add(new ArrayList<T>());
			return result;
		}
		// 处理n-1递归
		List<List<T>> combinations = findSortedCombinatinos(elements, n - 1);
		for (List<T> combination : combinations) {
			System.out.println("当前 n=" + n + " combinations = " + combinations.toString());
			for (T t : elements) {
				// 循环将元素添加到子集合中,如果子集合中已经包含此元素则不添加
				System.out.println("当前元素是　" + t + " combination是 " + combination);
				if (combination.contains(t)) {
					// 当n=2是 combinations中的值是[[a], [b], [c], [d]] 所以一次遍历 [a] [b] [c] [d]
					// 当前combination是[a] 所以包含
					System.out.println("由于当前 combination 是" + combination.toString() + "包含元素" + t);
					System.out.println("中断本层循环------------");
					continue;
				}
				List<T> list = new ArrayList<>();
				list.addAll(combination);
				// System.out.println("A处的combinations 的值是 "+combinations.toString());
				System.out.println("添加combination" + combination + "的所有值后list 的值是 " + list.toString());
				if (list.contains(t)) {
					System.out.println("当前 list 是" + list.toString() + "包含元素" + t);
					System.out.println("中断本层循环------------");
					continue;
				}
				list.add(t);
				System.out.println("list添加新元素后的list 的值是 " + list.toString());
				// 对元素排序,避免重复元素
				Collections.sort(list);
				System.out.println("排序后的list 的值是 " + list.toString());
				if (result.contains(list)) {
					System.out.println("当前 result 是" + result.toString() + "包含元素" + list);
					System.out.println("中断本层循环------------");
					continue;
				}
				result.add(list);
				System.out.println("循环后的result元素组 ：" + result.toString());
			}
		}
		return result;
	}

	public static <T extends Comparable<? super T>> List<List<T>> findSortedCombinatinos(Collection<T> elements) {
		List<List<T>> result = new ArrayList<>();
		for (int i = 0; i <= elements.size(); i++) {
			result.addAll(findSortedCombinatinos(elements, i));
		}
		return result;
	}

}
